home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung / Power-Programmierung (Tewi)(1994).iso / magazine / drdobbs / 1991 / 02 / nelson / model-1.c < prev    next >
C/C++ Source or Header  |  1990-06-02  |  3KB  |  107 lines
  1. /*
  2.  * Listing 9 -- model-1.c
  3.  *
  4.  * This is the modeling module for an order 0 fixed context
  5.  * data compression program.  This is a relatively simple model.
  6.  * The totals for all of the symbols are stored in an array accessed
  7.  * under the name "totals".  This array has valid indices from -1
  8.  * to 256.  The reason for having a -1 element is because the EOF
  9.  * symbols is included in the table, and it has a value of -1.
  10.  *
  11.  * The total count for all the symbols is stored in totals[256], and
  12.  * the low and high counts for symbol c are found in totals[c] and
  13.  * totals[c+1].  The major performance problem with this is that
  14.  * the update_model() routine on the average will have to increment
  15.  * 128 totals, a very high cost operation.
  16.  */
  17. #include <stdio.h>
  18. #include <stdlib.h>
  19. #include "coder.h"
  20. #include "model.h"
  21.  
  22. /*
  23.  * In order to create an array with indices -1 through 256, I have
  24.  * to do this funny declaration.  totals[-1] == storage[0].
  25.  */
  26. short int storage[ 258 ];
  27. short int *totals = storage + 1;
  28.  
  29. /*
  30.  * When the model is first started up, each symbols has a count of
  31.  * 1, which means a low value of c+1, and a high value of c+2.
  32.  */
  33. void initialize_model()
  34. {
  35.     short int i;
  36.  
  37.     for ( i = -1 ; i <= 256 ; i++ )
  38.         totals[ i ] = i + 1;
  39. }
  40.  
  41. /*
  42.  * Updating the model means incrementing every single count from
  43.  * the high value for the symbol on up to the total.  Then, there
  44.  * is a complication.  If the cumulative total has gone up to
  45.  * the maximum value, we need to rescale.  Fortunately, the rescale
  46.  * operation is relatively rare.
  47.  */
  48. void update_model( int symbol )
  49. {
  50.     int i;
  51.  
  52.     for ( symbol++ ; symbol <= 256; symbol++ )
  53.         totals[ symbol ]++;
  54.     if ( totals[ 256 ] == MAXIMUM_SCALE )
  55.     {
  56.         for ( i = 0 ; i <= 256 ; i++ )
  57.     {
  58.             totals[ i ] /= 2;
  59.             if ( totals[ i ] <= totals[ i-1 ] )
  60.                 totals[ i ] = totals[ i-1 ] + 1;
  61.     }
  62.     }
  63. }
  64.  
  65. /*
  66.  * Finding the low count, high count, and scale for a symbol
  67.  * is really easy, because of the way the totals are stored.
  68.  * This is the one redeeming feature of the data structure used
  69.  * in this implementation.  Note that this routine returns an
  70.  * int, but it is not used in this routine.  The return value
  71.  * from convert_int_to_symbol is used in model-2.c.
  72.  */
  73. int convert_int_to_symbol( int c, SYMBOL *s )
  74. {
  75.     s->scale = totals[ 256 ];
  76.     s->low_count = totals[ c ];
  77.     s->high_count = totals[ c+1 ];
  78.     return( 0 );
  79. }
  80.  
  81. /*
  82.  * Getting the scale for the current context is easy.
  83.  */
  84. void get_symbol_scale( SYMBOL *s )
  85. {
  86.     s->scale = totals[ 256 ];
  87. }
  88.  
  89. /*
  90.  * During decompression, we have to search through the table until
  91.  * we find the symbol that straddles the "count" parameter.  When
  92.  * it is found, it is returned. The reason for also setting the
  93.  * high count and low count is so that symbol can be properly removed
  94.  * from the arithmetic coded input.
  95.  */
  96. int convert_symbol_to_int( int count, SYMBOL *s)
  97. {
  98.     int c;
  99.  
  100.     for ( c = 255; count < totals[ c ] ; c-- )
  101.     ;
  102.     s->high_count = totals[ c+1 ];
  103.     s->low_count = totals[ c ];
  104.     return( c );
  105. }
  106.  
  107.